package com.wfm.leetcode.editor.cn;

import java.util.Arrays;

/**
 * 寻找两个正序数组的中位数
 * 2025-02-26 19:02:27
 */
class MedianOfTwoSortedArrays {

    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    // 最直观的解法就是，用归并排序把两个数组排序，然后找中位数
    // 时间复杂度：O(m+n)，空间复杂度：O(m+n)
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] nums = new int[nums1.length + nums2.length];
        // 合并两个有序的数组
        for (int i = 0, j = 0, k = 0; k < nums.length; k++) {
            if (i < nums1.length && j < nums2.length) {
                if (nums1[i] < nums2[j]) {
                    nums[k] = nums1[i];
                    i++;
                } else {
                    nums[k] = nums2[j];
                    j++;
                }
            } else if (i < nums1.length) {
                nums[k] = nums1[i];
                i++;
            }else if (j < nums2.length) {
                nums[k] = nums2[j];
                j++;
            }
        }
        // 计算中位数
        if (nums.length % 2 == 0) {
            return (nums[nums.length / 2] + nums[nums.length / 2 - 1]) / 2.0;
        } else {
            return nums[nums.length / 2];
        }
    }

    public double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        return 0;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new MedianOfTwoSortedArrays().new Solution();
        System.out.println(solution.findMedianSortedArrays(new int[]{1, 3}, new int[]{2}));
        System.out.println(solution.findMedianSortedArrays(new int[]{1, 2}, new int[]{3, 4}));
        System.out.println(solution.findMedianSortedArrays(new int[]{1, 2}, new int[]{3, 4, 5, 6}));
        // 期望9
        System.out.println(solution.findMedianSortedArrays(new int[]{1,2,3,4,5}, new int[]{6,7,8,9,10,11,12,13,14,15,16,17}));
    }
}